Technical Field
The present invention relates to a method and apparatus for solving a mixed integer programming problem.
Related Art
Since most combinatorial optimization problems are described as Mixed Integer Programming (or MIP) problems, it is important to solve MIP problems in a short amount of time in business. Linear Programming Relaxation (or LPR) has been used for solving MIP problems. According to LPR, all integer variables in the original MIP problem are relaxed to continuous variables, and the relaxed problem is solved to obtain information about the optimum solution of the original MIP problem. However, it still takes a long time to obtain an accurate solution for the original MIP problem, since it is often the case that the solution of the relaxed problem is not close to the solution of the original MIP problem.